import com.kiwi.nixu.common.LNode;

public class B如何从无序链表中移除重复项 {

    /**
     * 题目描述：给定一个没有排序的链表，去掉其重复项，
     * 并保留原顺序，如链表1→3→1→5→5→7，去掉重复项后变为1→3→5→7
     */


    /**
     * 思路：
     * 主要思路为：通过双重循环直接在链表上执行删除操作。
     * 外层循环用一个指针从第一个结点开始遍历整个链表，
     * 然后内层循环用另外一个指针遍历其余结点，
     * 将与外层循环遍历到的指针所指结点的数据域相同的结点删除
     * 假设外层循环从outerCur开始遍历，
     * 当内层循环指针innerCur遍历到上图实线所示的位置（outerCur.data==innerCur.data）时，
     * 此时需要把innerCur指向的结点删除。具体步骤如下：
     * 1）用tmp记录待删除的结点的地址。
     * 2）为了能够在删除tmp结点后继续遍历链表中其余的结点，
     * 使innerCur指针指向它的后继结点：innerCur=innerCur.next。3）从链表中删除tmp结点
     * <p>
     * 时间复杂度：时间复杂度为O（N^2）
     * <p>
     * 空间复杂度：空间复杂度为O（1）
     * <p>
     * 特点:
     * 由于这种方法采用双重循环对链表进行遍历，因此，时间复杂度为O（N^2）。
     * 其中，N为链表的长度。在遍历链表的过程中，
     * 使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，
     * 因此，空间复杂度为O（1）
     */
    private static class BA顺序删除 {
        public static void removeDup(LNode head) {
            if (head == null || head.next == null) {
                return;
            }
            LNode outerCur = head.next;//用于外层循环，指向链表的第一个结点
            LNode innerCur = null;
            LNode innerPre = null;
            for (; outerCur != null; outerCur = outerCur.next) {
                for (innerCur = outerCur.next, innerPre = outerCur; innerCur != null; ) {
                    //找到重复的节点并删除
                    if (outerCur.data.equals(innerCur.data)) {
                        innerPre.next = innerCur.next;
                        innerCur = innerCur.next;
                    } else {
                        innerPre = innerCur;
                        innerCur = innerCur.next;
                    }
                }
            }
        }

        public static void main(String[] args) {

        }
    }

    /**
     * 思路：
     * 主要思路为：对于结点cur，首先递归地删除以cur.next为首的子链表中重复的结点，
     * 接着从以cur.next为首的子链表中找出与cur有着相同数据域的结点并删除。实现代码如下
     * <p>
     * 时间复杂度：时间复杂度为O（N^2
     * <p>
     * 空间复杂度：
     * <p>
     * 特点:这种方法与方法一类似，
     * 从本质上而言，由于这种方法需要对链表进行双重遍历，因此，时间复杂度为O（N^2）。
     * 其中，N为链表的长度。由于递归法会增加许多额外的函数调用，
     * 因此，从理论上讲，该方法效率比方法一低
     */
    private class BB递归方法 {

    }

    /**
     * 思路：HashSet
     * 时间复杂度：
     * 空间复杂度：
     * 优点：
     * 缺点
     */
    private class BC空间换时间 {

    }

    /**
     * 思路：
     * 上述介绍的方法也适用于链表有序的情况，但是由于以上方法没有充分利用到链表有序这个条件，
     * 因此，算法的性能肯定不是最优的。本题中，由于链表具有有序性，因此，不需要对链表进行两次遍历。
     * 所以，有如下思路：用cur 指向链表第一个结点，
     * 此时需要分为以下两种情况讨论。
     * 1）如果cur.data==cur.next.data，那么删除cur.next结点。
     * 2）如果cur.data!=cur.next.data，那么cur=cur.next，继续遍历其余结点
     * <p>
     * 时间复杂度：
     * 空间复杂度：
     * 优点：
     * 缺点
     */
    private class BD如何从有序链表中移除重复项 {

    }
}
